#include <bits/stdc++.h>
using namespace std;

/*
2561. 重排水果
已解答
困难
相关标签
premium lock icon
相关企业
提示
你有两个果篮，每个果篮中有 n 个水果。给你两个下标从 0 开始的整数数组 basket1 和 basket2 ，用以表示两个果篮中每个水果的交换成本。你想要让两个果篮相等。为此，可以根据需要多次执行下述操作：

选中两个下标 i 和 j ，并交换 basket1 中的第 i 个水果和 basket2 中的第 j 个水果。
交换的成本是 min(basket1i,basket2j) 。
根据果篮中水果的成本进行排序，如果排序后结果完全相同，则认为两个果篮相等。

返回使两个果篮相等的最小交换成本，如果无法使两个果篮相等，则返回 -1 。

 

示例 1：

输入：basket1 = [4,2,2,2], basket2 = [1,4,1,2]
输出：1
解释：交换 basket1 中下标为 1 的水果和 basket2 中下标为 0 的水果，交换的成本为 1 。此时，basket1 = [4,1,2,2] 且 basket2 = [2,4,1,2] 。重排两个数组，发现二者相等。
示例 2：

输入：basket1 = [2,3,4,1], basket2 = [3,2,5,1]
输出：-1
解释：可以证明无法使两个果篮相等。
*/

// 法一
class Solution {
public:
    using ll = long long;
    long long minCost(vector<int>& basket1, vector<int>& basket2) {
        unordered_map<int, int> cnt;
        ll mn = INT_MAX;        // 全局最小

        // 统计两个篮子里面 水果出现次数 计算全局最小
        for (int x : basket1) {
            cnt[x]++;
            if (x < mn) mn = x;
        }
        for (int x : basket2) {
            cnt[x]--;
            if (x < mn) mn = x;
        }

        // 交换容器 
        vector<ll> arr;
        for (auto &[x, c] : cnt) {
            // 奇数不可行
            if (c % 2 != 0)     return -1;  // 不可用
            int tmp = abs(c) / 2;
            // 逐个进待交换列表
            while (tmp--)  arr.push_back(x);
        }
        sort(arr.begin(), arr.end());

        ll ans = 0;
        // 交换次数应该是列表长度的一半
        for (int i = 0; i < arr.size() / 2; i++) {
            // 选择最小成本
            ans += min(arr[i], 2 * mn);
        }

        return ans;
    }
};

// 法二
class Solution {
public:
    long long minCost(vector<int>& basket1, vector<int>& basket2) {
        int m = INT_MAX; // 初始化全局最小值，用于后续优化交换策略
        unordered_map<int, int> frequency_map; // 记录每个水果在两个篮子中的数量差异
        
        // 遍历两个篮子，统计差异并更新全局最小值
        for (int b1 : basket1) {
            frequency_map[b1]++; // basket1 中出现的水果计数+1
            m = min(m, b1);     // 更新全局最小值
        }
        for (int b2 : basket2) {
            frequency_map[b2]--; // basket2 中出现的水果计数-1
            m = min(m, b2);      // 更新全局最小值
        }
        
        vector<int> merge; // 存储需要交换的水果
        for (auto [k, c] : frequency_map) {
            if (c % 2 != 0) { // 检查差异是否为奇数
                return -1;     // 若为奇数，无法平分，直接返回-1
            }
            // 将差异绝对值的一半数量的水果加入merge（每个水果需交换的次数）
            for (int i = 0; i < abs(c) / 2; ++i) {
                merge.push_back(k);
            }
        }
        
        // 部分排序：仅将最小的前 n/2 个元素移到左侧（无需完全排序）
        nth_element(merge.begin(), merge.begin() + merge.size() / 2, merge.end());
        
        // 累加前一半元素的最小交换成本
        return accumulate(merge.begin(), merge.begin() + merge.size() / 2, 0ll,
            [&](long long res, int x) -> long long {
                // 成本选择：直接交换成本x 或 间接交换成本2*m（取最小值）
                return res + min(2 * static_cast<long long>(m), static_cast<long long>(x));
            }
        );
    }
};